package org.sudoku.solver;

import static org.sudoku.solver.Sudoku.*;

import java.util.ArrayList;

/**
 * A 2-level probabilistic solver. This probabilistic solver makes assumptions
 * to solve when the inference based solver halts. By 2-level it means that this
 * solver takes for granted that there will be at least one cell for which the
 * inference based solver concludes that it can take one of exactly 2 digits.
 * This solver searches for such a cell and assumes one of the 2 digits and
 * invokes inference solving on it until the grid remains consistent or is
 * solved or there is no progress. By consistent we mean that no row, column or
 * cube should have more than one cells with the same digit. If there is
 * incosistency then it means that the assumption is wrong. If the problem gets
 * solved or there is no progress it means that the assumption is correct. When
 * there is no progress, this assumption based solution is applied recursively.
 * 
 * @author shivkumar cm
 * 
 */
public class ProbabilisticSolver extends SimpleSolver implements I9X9Solver,
		Cloneable {

	public void printFacts() {
		foreachCell(new ForeachCell() {
			public void process(int row, int col) {
				if (isKnown(row, col)) {
					return;
				}
				int bitString = m_grid[row][col];
				System.out.printf("Cell [%d, %d]: ", row, col);
				for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
					if (((1 << i) & bitString) > 0) {
						System.out.printf("%d, ", i);
					}
				}
				System.out.println();
			}
		});
	}

	protected int m_assumptions = 0;

	@Override
	public int solve() {

		// Solve using simple solver to see if it halts
		int steps = super.solve();
		if (super.solved()) {
			System.out.printf("Solved with %d assumptions", m_assumptions);
			return steps;
		}

		// A 2-level probabilistic solver - assumes that there will be atleast
		// one cell for which we can say that it has one of two given digits
		int arr[] = getCellWithOptions(2);

		// Unable to solve
		if (arr == null) {
			System.out.println("Probabilistic solver failed...");
			return steps;
		}
		int row = arr[ROW], col = arr[COL], digit1 = arr[2], digit2 = arr[3];

		if (assume(row, col, digit1)) {
			set(row, col, digit1);
		} else {
			System.out.printf("Setting %d at [%d, %d]\n", digit2, row, col);
			set(row, col, digit2);
		}
		return solve();
	}

	/**
	 * Applies the assumption that position [row, col] is digit
	 * 
	 * @return true if the assumption keeps the grid consistent with further
	 *         steps in solving
	 */
	protected boolean assume(int row, int col, int digit) {
		++m_assumptions;
		System.out.printf("Dry run assuming %d at [%d, %d]\n", digit, row, col);

		ProbabilisticSolver clone = (ProbabilisticSolver) this.clone();

		ArrayList<int[]> consistencyCheckList = new ArrayList<int[]>();
		consistencyCheckList.add(new int[] { row, col });
		clone.set(row, col, digit);
		boolean consistent = true, progressing = true;

		while ((consistent = clone.isConsistent(consistencyCheckList))
				&& !clone.solved() && progressing) {
			consistencyCheckList.clear();
			progressing = clone.inferAndApply();
			for (int triplet[] : clone.getInferences()) {
				consistencyCheckList
						.add(new int[] { triplet[ROW], triplet[COL] });
			}
		}

		if (consistent) {
			absorbFromCloneIfAssumptionCorrect(clone);
		}
		return consistent;
	}

	protected void absorbFromCloneIfAssumptionCorrect(ProbabilisticSolver clone) {
		// Just replace the grid
		this.m_grid = clone.m_grid;
		// No need to copy inferences as either the problem is solved or is not
		// progressinng
		// Should not copy assumptions
		this.m_knownCells = clone.m_knownCells;
	}

	/**
	 * @param count
	 *            The number of known options/possibilities for a cell
	 * @return array of length count + 2 with first two positions having the row
	 *         and col indexes. Rest of the positions have the known options.
	 *         Example- if count is 2, it means that the method is expected to
	 *         return the row and col index of any cell that has exactly 2
	 *         posibilities, together with these 2 posibilities.
	 */
	protected int[] getCellWithOptions(final int count) {
		int retval[] = new int[count + 2];
		boolean found_flag = false;
		for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
			for (int j = SUDOKU_BASE; j <= SUDOKU_MAX; ++j) {
				if (isKnown(i, j)) {
					continue;
				}
				int bitString = m_grid[i][j];
				int cur_count = 0;
				for (int k = SUDOKU_BASE; k <= SUDOKU_MAX; ++k) {
					if (((1 << k) & bitString) > 0) {
						++cur_count;
					}
				}
				if (cur_count == count) {
					found_flag = true;
					retval[0] = i;
					retval[1] = j;
					int l = 2;
					for (int k = SUDOKU_BASE; k <= SUDOKU_MAX; ++k) {
						if (((1 << k) & bitString) > 0) {
							retval[l++] = k;
						}
					}
					break;
				}
			}
			if (found_flag) {
				break;
			}
		}
		return found_flag ? retval : null;
	}

	protected boolean isConsistentRow(int row) {
		boolean found_digit[] = new boolean[GRID_SIZE];
		for (int j = SUDOKU_BASE; j <= SUDOKU_MAX; ++j) {
			if (isKnown(row, j)) {
				if (found_digit[get(row, j)]) {
					return false;
				} else {
					found_digit[get(row, j)] = true;
				}
			}
		}
		return true;
	}

	protected boolean isConsistentCol(int col) {
		boolean found_digit[] = new boolean[GRID_SIZE];
		for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
			if (isKnown(i, col)) {
				if (found_digit[get(i, col)]) {
					return false;
				} else {
					found_digit[get(i, col)] = true;
				}
			}
		}
		return true;
	}

	protected boolean isConsistentCube(int row, int col) {
		int baseRow = cubeBase(row), baseCol = cubeBase(col);
		boolean found_digit[] = new boolean[GRID_SIZE];
		for (int i = baseRow; i < baseRow + CUBE_SIZE; ++i) {
			for (int j = baseCol; j < baseCol + CUBE_SIZE; ++j) {
				if (isKnown(i, j)) {
					if (found_digit[get(i, j)]) {
						return false;
					} else {
						found_digit[get(i, j)] = true;
					}
				}
			}
		}
		return true;
	}

	protected boolean isConsistent(int row, int col) {
		return isConsistentRow(row) && isConsistentCol(col)
				&& isConsistentCube(row, col);
	}

	protected boolean isConsistent(ArrayList<int[]> consistencyChecklist) {
		for (int[] cell : consistencyChecklist) {
			if (!isConsistent(cell[ROW], cell[COL])) {
				return false;
			}
		}
		return true;
	}

	@Override
	protected Object clone() {
		ProbabilisticSolver clone = null;
		try {
			clone = (ProbabilisticSolver) super.clone();
		} catch (CloneNotSupportedException ex) {
			System.out
					.println("Unexpected clone unsupported exception. Aborting...");
			System.exit(1);
		}
		clone.m_inferred = new ArrayList<int[]>();
		// choosing not to copy over the inferred array as it is temporary

		clone.m_grid = new int[GRID_SIZE][GRID_SIZE];
		for (int i = SUDOKU_BASE; i <= SUDOKU_MAX; ++i) {
			for (int j = SUDOKU_BASE; j <= SUDOKU_MAX; ++j) {
				clone.m_grid[i][j] = m_grid[i][j];
			}
		}

		return clone;
	}
}
